package algorithms.recursion;

public class MouseMaze {
	private int startI;
	private int startJ;
	private int endI;
	private int endJ;
	private boolean success;
	public static void main(String[] args) {
		int[][] maze = {
				{2,2,2,2,2,2,2},
				{2,0,0,0,0,0,2},
				{2,0,2,0,2,0,2},
				{2,0,0,2,0,2,2},
				{2,2,0,2,0,2,2},
				{2,0,0,0,0,0,2},
				{2,2,2,2,2,2,2},
		};
		System.out.println("迷宫：");
		for(int[] a1 : maze) {
			for(int a : a1) {
				if(a == 2) {
					System.out.print("#");
				} else {
					System.out.print(" ");
				}
			}
			System.out.println();
		}
		MouseMaze mouse = new MouseMaze();
		mouse.startI =1;
		mouse.startJ = 1;
		mouse.endI = 5;
		mouse.endJ = 4;
		mouse.go(maze);
		for(int[] a1 : maze) {
			for(int a : a1) {
				if(a == 2) {
					System.out.print("#");
				} else if(a == 0){
					System.out.print(" ");
				} else {
					System.out.print("^");
				}
			}
			System.out.println();
		}
	}
	
	public boolean go(int[][] maze) {
		return visit(maze, startI, startJ);
	}

	private boolean visit(int[][] maze, int i, int j) {
		maze[i][j] = 1;
		
		if(i == endI && j == endJ) {
			success = true;
		}
		
		if(!success && maze[i][j + 1] == 0) {
			visit(maze, i, j + 1);
		}
		if(!success && maze[i + 1][j] == 0) {
			visit(maze, i + 1, j);
		}
		
		if(!success && maze[i][j - 1] == 0) {
			visit(maze, i, j - 1);
		}
		if(!success && maze[i - 1][j] == 0) {
			visit(maze, i - 1, j);
		}
		
		if(!success)
			maze[i][j] = 0;
		return success;
	}
	
	
}
